挿入ソート Insertion sort
Sorting ソート 整列アルゴリズム Algorithmsの一種
手持ちトランプを並び替える時
1枚ずつ取り出して、並びの適切な位置に挿入して並べ替える
特徴
入力データが予め整列されていると早い
改良版 Shellsort シェルソート
in-place Algorithms
安定性 Algorithms
O(n**2)では高速
スタートが0でなく1からスタート
並べられた列に要素を正しい位置に挿入していく
利点
ソート時に用いるメモリが少ない
使うべき状況
配列 Arrayの要素数が少ない時
22以下 by V8
V8では、10以下で使ってた模様
配列 Arrayがほぼソートされている時
重複する要素が存在する時
table:insertionSort
Name Best Average Worst Memory Stable Comments
Insertion sort O(n) O(n**2) O(n**2) 1 True
GitHub.icontypescript-algorithms/src/algorithms/sorting/insertionSort at master · KiichiSugihara/typescript-algorithms
参考
javascript-algorithms/src/algorithms/sorting/insertion-sort at master · KiichiSugihara/javascript-algorithms
挿入ソートについて - kakts-log
アルゴリズム 挿入ソートの実装（Javascript編） | Tips of Rubbish
良さげなので、改善で盛り込む